1. Field of the Invention
The present invention relates to an internal interleaver for turbo coding, referred to as a prime number interleaver, which has been normalized in wideband DS-CDMA (W-CDMA) that has been standardized as one of radio access networks (RAN) for a third-generation mobile communication system (IMT2000).
2. Description of the Related Art
Wideband DS-CDMA (W-CDMA) has been standardized as one of radio access networks (RAN) for the third-generation mobile communication system (IMT2000), and a turbo code internal interleaver, referred to as the “prime number interleaver,” has been normalized in the standard. Detailed description thereof is disclosed in “3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Multiplexing And Channel Coding (FDD)” (Release 1999), 3GPP TS25. 213 V3.10.0 (2002-06), Section 4.2.3.2.3, Turbo Code Internal Interleaver, pp. 16-19. The following description is based on this document.
In an interleaver for the turbo code normalized in Standard 3GPP TS25.212 of IMT2000 (W-CDMA), intra-row permutation pattern U[i][j], which is indispensable for encoding data to be transmitted, is defined as follows using r[i] which is defined later:U[i][j]=s[(j*r[i])*mod(p−1)]=s[x[i][j]]  (1)
where x[i][j]=(j*r[i])*mod(p−1)
Herein, r[i] is defined as follows using inter-row permutation pattern T[i], and prime number sequence q[i] which is defined later:r[T[i]]=q[i]  (2)
Prime number sequence q[i] is defined as follows using the number of rows R and prime number p of the interleaver:q[0]=1                where q[i] for i=1, 2, . . . , R−1, is a minimum prime number which satisfiesg.c.d(q[i],p−1)=1 and q[i]>6, and q[i]>q[i−1]  (3)        where g. c. d(x,y) is the greatest common divisor of x and y.        
Referring to FIGS. 1A and 1B, values for prime number sequence q[i] are exemplified for each value of prime number p when the number of rows R in the interleaver is equal to 20 (R=20).
As described above, intra-row permutation pattern U[i][j] is calculated using prime number p, base sequence s[j], inter-row permutation pattern T[i], and prime number sequence q[i].
In a mobile telephone and the like in IMT2000, a data length is first calculated for data to be transmitted. Then, prime number p, base sequence s[j], inter-row permutation pattern T[i], and prime number sequence q[i] are determined based on the calculated data length (or the size of a matrix for storing the data to be transmitted). Then, intra-row permutation pattern U[i][j] is calculated based on these values. Next, transmission data is encoded based on the calculated intra-row permutation pattern U[i][j] and inter-row permutation pattern T[i], and the encoded transmission data is transmitted to a mobile telephone network. Another mobile telephone which has received the encoded data, decodes the received encoded data based on intra-row permutation pattern U[i][j] and inter-row permutation pattern T[i] which have been calculated in a similar manner.
Prime number p, base sequence s[j], and prime number sequence q[i] can be uniquely determined from the length of data to be transmitted (or the size of a matrix which stores the data to be transmitted). Prime number sequence q[i] has been shown in Equation (3) and FIGS. 1A, 1B. Also, the present applicant has already filed a method of efficiently calculating base sequence s[j] (Japanese Patent Application No. 2003-298493). For inter-row permutation pattern T[i], there are four fixed patterns, any one of which is selected.
As described above, intra-row permutation pattern U[i][j] is calculated using prime number p, base sequence s[j], inter-row permutation pattern T[i], and prime number sequence q[i]. However, for simplifying the calculation, intra-row permutation pattern U[i][j] is typically calculated after y[i], defined as follows, is determined as an intermediate value to calculate intra-row permutation pattern U[i][j]:y[i]=w[i][1]=q[i]*mod(p−1)  (4)
where w[i][j] is defined as follows:
                                                                                          w                  ⁡                                      [                    i                    ]                                                  ⁡                                  [                  j                  ]                                            =                                                                    x                    ⁡                                          [                                              T                        ⁡                                                  [                          i                          ]                                                                    ]                                                        ⁡                                      [                    j                    ]                                                  =                                                      (                                          j                      *                                              r                        ⁡                                                  [                                                      T                            ⁡                                                          [                              i                              ]                                                                                ]                                                                                      )                                    *                                      mod                    (                                          p                      -                      1                                        )                                                                                                                          =                                                (                                      j                    *                                          q                      ⁡                                              [                        i                        ]                                                                              )                                *                                  mod                  ⁡                                      (                                          p                      -                      1                                        )                                                                                                          (        5        )            
In the following, description will be made of a method of calculating intra-row permutation pattern U[i][j] according to the prior art, using a specific example.
First, prime number p, base sequence s[j], inter-row permutation pattern T[i], and prime number sequence q[i] are determined from the data length of data to be transmitted. Assume for example that p, s[j], T[i], q[i] have been determined as follows:
Setting Parametersp=7s[i]=[1,3,2,6,4,5](j=0-5)T[i]=[4,3,2,1,0] (i=0-4)(R=5)q[i]=[1,7,11,13,17] (i=0-4)(R=5)
First, intermediate value y[i] is calculated as follows based on Equation (4), p, q[i]. FIG. 2 shows a flow chart of the procedure to find y[i].
Calculation Process 1y[0]=q[0]*mod(7−1)=1*mod 6=1y[1]=q[1]*mod(7−1)=7*mod 6=1y[2]=q[2]*mod(7−1)=11*mod 6=5y[3]=q[3]*mod(7−1)=13*mod 6=1y[4]=q[4]*mod(7−1)=17*mod 6=5
Next, x[i][1] is calculated as follows based on y[i] calculated in Calculation Process 1, T[i], and Equations (4), (5):
Calculation Process 2y[i]=w[i][1]=x[T[i]][1]y[0]=w[0][1]=[T[0]][1]=x[4][1]=1y[1]=w[1][1]=[T[1]][1]=x[3][1]=1y[2]=w[2][1]=[T[2]][1]=x[2][1]=5y[3]=w[3][1]=[T[3]][1]=x[1][1]=1y[4]=w[4][1]=[T[4]][1]=x[0][1]=5Therefore, x[i][1]=[5, 1, 5, 1, 1] (I=0 to 4) (R=5)
Next, x[i][j] is calculated based on x[i][1] calculated in Calculation Process 2 and prime number p with reference to Equation (1), without performing a remainder calculation, as follows:
Calculation Process 3x[0][0]=0x[0][1]=5x[0][2]=x[0][1]+x[0][1]−(p−1)=5+5−6=4x[0][3]=x[0][2]+x[0][1]−(p−1)=4+5−6=3x[0][4]=x[0][3]+x[0][1]−(p−1)=3+5−6=2x[0][5]=x[0][4]+x[0][1]−(p−1)=2+5−6=1
(Since each of x[0][1]+x[0][1], x[0][2]+x[0][1], x[0][3]+x[0][1], x[0][4]+x[0][1] is larger than p−1, p−1 is subtracted from the value.)x[1][0]=0x[1][1]=1x[1][2]=x[1][1]+x[1][1]=1+1=2x[1][3]=x[1][2]+x[1][1]=2+1=3x[1][4]=x[1][3]+x[1][1]=3+1=4x[1][5]=x[1][4]+x[1][1]=4+1=5
(Since each of x[0][1]+x[0][1], x[0][2]+x[0][1], x[0][3]+x[0][1], x[0][4]+x[0][1] is smaller than p−1, the value is output as is.)x[2][0]=0x[2][1]=5x[2][2]=x[2][1]+x[2][1]−(p−1)=5+5−6=4x[2][3]=x[2][2]+x[2][1]−(p−1)=4+5−6=3x[2][4]=x[2][3]+x[2][1]−(p−1)=3+5−6=2x[2][5]=x[2][4]+x[2][1]−(p−1)=2+5−6=1
(Since each of x[0][1]+x[0][1], x[0][2]+x[0][1], x[0][3]+x[0][1], x[0][4]+x[0][1] is larger than p−1, p−1 is subtracted from the value.)x[3][0]=0x[3][1]=1x[3][2]=x[3][1]+x[3][1]=1+1=2x[3][3]=x[3][2]+x[3][1]=2+1=3x[3][4]=x[3][3]+x[3][1]=3+1=4x[3][5]=x[3][4]+x[3][1]=4+1=5
(Since each of x[0][1]+x[0][1], x[0][2]+x[0][1], x[0][3]+x[0][1], x[0][4]+x[0][1] is smaller than p−1, the value is output as is.)x[4][0]=0x[4][1]=5x[4][2]=x[4][1]+x[4][1]−(p−1)=5+5−6=4x[4][3]=x[4][2]+x[4][1]−(p−1)=4+5−6=3x[4][4]=x[4][3]+x[4][1]−(p−1)=3+5−6=2x[4][5]=x[4][4]+x[4][1]−(p−1)=2+5−6=1
(Since each of x[0][1]+x[0][1], x[0][2]+x[0][1], x[0][3]+x[0][1], x[0][4]+x[0][1] is larger than p−1, p−1 is subtracted from the value.)
Finally, U[i] [j] is calculated based on x[i][j], s[i], and Equation (1).
Calculation Process 4U[0][0]=s[x[0][0]]=s[0]=1U[0][1]=s[x[0][1]]=s[5]=5U[0][2]=s[x[0][2]]=s[4]=4U[0][3]=s[x[0][3]]=s[3]=6U[0][4]=s[x[0][4]]=s[2]=2U[0][5]=s[x[0][5]]=s[1]=3U[1][0]=s[x[1][0]]=s[0]=1U[1][1]=s[x[1][1]]=s[1]=3U[1][2]=s[x[1][2]]=s[2]=2U[1][3]=s[x[1][3]]=s[3]=6U[1][4]=s[x[1][4]]=s[4]=4U[1][5]=s[x[1][5]]=s[5]=5U[2][0]=s[x[2][0]]=s[0]=1U[2][1]=s[x[2][1]]=s[5]=5U[2][2]=s[x[2][2]]=s[4]=4U[2][3]=s[x[2][3]]=s[3]=6U[2][4]=s[x[2][4]]=s[2]=2U[2][5]=s[x[2][5]]=s[1]=3U[3][0]=s[x[3][0]]=s[0]=1U[3][1]=s[x[3][1]]=s[1]=3U[3][2]=s[x[3][2]]=s[2]=2U[3][3]=s[x[3][3]]=s[3]=6U[3][4]=s[x[3][4]]=s[4]=4U[3][5]=s[x[3][5]]=s[5]=5U[4][0]=s[x[4][0]]=s[0]=1U[4][1]=s[x[4][1]]=s[5]=5U[4][2]=s[x[4][2]]=s[4]=4U[4][3]=s[x[4][3]]=s[3]=6U[4][4]=s[x[4][4]]=s[2]=2U[4][5]=s[x[4][5]]=s[1]=3
In processors used in mobile telephones and the like, limitations in their circuit size often force them to perform the remainder calculations digit by digit. When a processor has a data width of 16 bits, 16 clocks are required for the calculation of each row of y[i] (step 43 in FIG. 2) in Calculation Process 1. Further, assuming that two clocks are required for a conditional branch (step 45) in FIG. 2, and one clock is required for other processing (step 44) in FIG. 2, 19 clocks are required for each execution of step 43 to step 45 in FIG. 2. As a result, Calculation Process 1 requires a total of 19*R clocks (since the maximum value of R is 20, 380 clocks are required at maximum).